//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 
//prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。 
//
// 
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 
// 
//
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：[0,1]
//解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出：[0,2,1,3]
//解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
//因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 
//
// 示例 3： 
//
// 
//输入：numCourses = 1, prerequisites = []
//输出：[0]
// 
//
// 
//提示：
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// 所有[ai, bi] 互不相同 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 860 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-09-10 18:58:16
 * @description 210.课程表 II
 */
public class CourseScheduleIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CourseScheduleIi().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //边
		 List<List<Integer>> edge;
		 //是否访问
		 int [] vis;
		 //结果
		 int[] res;
		 //全局是否有环
		 boolean valid;
		 //结果的下标
		 int index;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
		res = new int[numCourses];
		edge=new ArrayList<>();
		valid=true;
		vis=new int[numCourses];
		index=numCourses-1;
		//至少有这么多条边
		for (int i = 0; i < numCourses; i++) {
			edge.add(new ArrayList<>());
		}
		//把每一个课程的前置课程加进去
		for (int[] prerequisite : prerequisites) {
			edge.get(prerequisite[1]).add(prerequisite[0]);
		}
		//把每一个没搜索的点进行dfs
		for (int i = 0; i < numCourses; i++) {
			if(vis[i]==0){
				dfs(i);
			}
		}
		//有环就算了
		if(!valid){
			return new int[0];
		}
		return res;

	}

	private void dfs(int u){
		//搜索中
		vis[u]=1;
		for (int v : edge.get(u)) {
			//没有搜
			if(vis[v]==0){
				//搜他相邻的
				dfs(v);
				//有环
				if(!valid){
					return;
				}
			}
			//如果搜到搜索中的，说明有环
			else if(vis[v]==1){
				valid=false;
				return;
			}
		}
		//搜完了
		vis[u]=2;
		//加入到结果中
		res[index--]=u;
	}
	/*从出度入度0开始，bfs*/
	public int[] findOrder1(int numCourses, int[][] prerequisites){
		Queue<Integer>q=new LinkedList<>();
		edge=new ArrayList<>();
		vis=new int[numCourses];
		res=new int[numCourses];
		for (int i = 0; i < numCourses; i++) {
			edge.add(new ArrayList<>());
		}
		for (int[] prerequisite : prerequisites) {
			edge.get(prerequisite[1]).add(prerequisite[0]);
			vis[prerequisite[0]]++;
		}

		for (int i = 0; i < numCourses; i++) {
			//把入度为0的点加入队列
			if(vis[i]==0){
				q.offer(i);
			}
		}
		int count=0;
		while (!q.isEmpty()){
			++count;
			int u =q.poll();
			res[index++]=u;
			for (int v : edge.get(u)) {
				//v的入度-1,减的u
				--vis[v];
				if(vis[v]==0){
					q.offer(v);
				}
			}
		}
		return count==numCourses?res:new int[0];

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
